Groupe TP41 : Floréal RISSO et Téo TINARRAGE
L’implémentation utilisé est celle proposée dans le sujet.
L’implémentation utilisée est celle proposée en exemple, étendue par
nous-même. Elle applique l’algorithme et réalise les tests sur
ses résultats (au lieu d’avoir un script de test qui appelle un
programme implémentant l’algorithme, tout est réalisé par un seul
programme).
Les fichiers de l’implémentation d’origine sont présents tels quels et
nos ajouts se situent dans d’autres classes qui exploitent les
précédentes.
Entrées : liste non-vide d’arcs (orientés ou
non) pondérés (c’est à dire numéro de sommet de départ, numéro de
sommet d’arrivée, poids(float)) décrivant un graphe (l’existence d’un
sommet est impliquée par l’existence d’un arc l’ayant comme extrémité),
ainsi que le numéro du sommet de départ pour le calcul des
distances, au format JSON*
Sortie : *Distance* entre chaque sommet du graphe et le
sommet de départ choisi, (“Distance” désignant la somme des poids des
arcs parcourus par le chemin minimisant cette somme)
*structure attendue du JSON :
Pour les données d’entrée
{
"graphs" : [
{
"departDijkstra" : <numéro du sommet de départ de l'algo>,
"estOriente" : <booléen>
"chemins" : [
{
"depart" : <numéro sommet de départ>,
"arrivée" : <numéro sommet d'arrivée>,
"poids" : <poids de l'arc (flottant)>
} ,
...
]
}
]
}Entrée : Résultats attendus (oracles) pour
l’application de l’algo aux données d’entrées spécifiées
Sortie : résultat des tests.
Pour les résultats attendus :
{
"results": [
"distances" : [...] <liste des distances attendues>
"parents" : [...] <liste des parents de chaque sommets>
]
}Le programme de test est test.java. Son fonctionnement est simple, dans un premier temps il lit les jeux de tests et les oracles.
private static final String testFile = "./tests.json";
private static final String resultFile = "./results.json";
// La fonction qui lit les jeux de tests ecrit dans le fichier "./tests.json".
private static Tester getTests();
// La classe qui contient le contenue du fichier de test.
public static class Tester {
private Graph[] graphs; // les graphes
private int[] startDijsktra; // le sommet de depart
}
// La fonction qui lit les oracles
private static Result[] getResults();
// La classe qui contient le resultat attendu d'un jeu de test.
public class Result {
private float[] distances;
private int[] parents;
}Ensuite, on appel la fonction qui calcule la distance de Dijsktra sur l’ensemble des jeux de tests et on compare le résultat attendu du résultat obtenu.
// Parcourt des jeux de tests
for(Graph graph : graphs) {
// Calcul du resultat
Result result = TestGraphs.Dijkstra(graph,tester.startDijsktra[i]);
// Comparaison du resultat au resultat attendu
TestResult testResult = expectedResults[i].equals(result);
}La fonction de comparaison donne de nombreuses informations sur les différences afin d’aider le débogue et à la fin du programme il est indiqué le nombre de test réussi sur le nombre de test tenté.
// La fonction qui vérifie l'egalité des resultats attendue et calculé.
public TestResult equals(Result r) {
// Des branchement if / else
// ...
return new TestResult("Un message expliquant la différence...");
}
// La classe retournée par equals :
public class TestResult {
// Les resultats sont les mêmes
private boolean areEquals;
// Le message d'erreur
private String error;
}
// Enfin le print final qui compare les nombres de test reussi et echoué.
System.out.println("Resultat : ["+passed+"/"+i+"]");Voici les captures d’écrans montrant les lignes de code exécutés avec le jeu donné dans l’énoncé.
{
"graphs": [
{
"estOriente": false,
"departDijkstra": 0,
"sommets": 6,
"chemins": [
{
"depart": 0,
"arrivee": 1,
"poids": 2.0
},
{
"depart": 0,
"arrivee": 4,
"poids": 3.0
},
{
"depart": 1,
"arrivee": 4,
"poids": 4.0
},
{
"depart": 1,
"arrivee": 2,
"poids": 5.0
},
{
"depart": 1,
"arrivee": 5,
"poids": 2.0
},
{
"depart": 2,
"arrivee": 3,
"poids": 2.0
},
{
"depart": 2,
"arrivee": 5,
"poids": 4.0
},
{
"depart": 3,
"arrivee": 4,
"poids": 2.0
},
{
"depart": 3,
"arrivee": 5,
"poids": 5.0
},
{
"depart": 4,
"arrivee": 5,
"poids": 2.0
}
]
}
]
}{
"results": [
{
"distances" :[0.0, 2.0, 7.0,3.4028235E38,3.0,4.0],
"parents" : [-1,0,1,-1,0,1]
}
]
}
Dans la version originale de l’implémentation, qui nous est donnée dans le sujet, n’importe quelle suite de test passait par toutes les instructions, à l’exception de certains fonctions utilitaires qui ne sont jamais appelées.
Cependant, dans notre version (qui ajoute un système de lecture
d’entrée sous forme de fichier JSON, et la comparaison de la sortie avec
la sortie attendue, ce qui permet l’automatisation des tests, là où avec
l’implémentatation initiale les données d’entrée devaient se trouver
dans le code directement), Certaines instructions ne pourront pas être
éxécutées, notament celles liées au contrôle d’erreur : en effet, on
trouve beaucoup de conditions de la forme “si erreur, afficher qque
chose, et terminer le programme” : ainsi, s’il n’y a pas d’erreur les
instructions d’affichage ne sont pas couvertes, s’il y a erreur le reste
du programme n’est pas éxécuté.
Autre exemple du même type, toutes les séquences de lecture/écriture de
fichier impliquent l’utilisation d’un bloc try/catch :
Globalement il est impossible de passer par toutes les instructions du programme, cependant les instructions servant à réaliser l’algorithme en lui-même peuvent être toutes traversées par plus ou moins n’importe quelle suite de tests.
Java restreint fortement les possibilités dans les tests, car les types sont static et fort, ainsi il n’est pas possible de donner un mauvais type ou une valeur trop grande. Alors nous ne pourront pas tester les classes invalides, ni un nombre de sommet inférieure ou égale à zéro. Mais nous allons testé les poids (négatifs, nul, positif) et si un graphe est orienté ou non.
| Variable | poid<0.0 | poid=0 | poid>0.0 | poid in [-inf,inf] |
|---|---|---|---|---|
| Orienté | Test 2 | Test 1 | Test4 | |
| Non orienté | Test 3 | Test 5 |
(cf. voir tests.json et results.json)
Il est difficile de trouver des mutants très pertinent vu la simplicité du code et le faible nombre d’instructions.
// TestGraph.java ligne 71
// ">" devient ">="
if (v.getDistance() >= u.getDistance() + e.getWeight()) {
v.setDistance(u.getDistance() + e.getWeight());
v.setParent(u);
parents[v.getId()] = v.getParent().getId();
}Ce mutant est choisi, car il est souvent compliqué de choisir entre “supérieure >” et “supérieure ou égale >=”.
[V] - Test : 0
[X] - Test : 1
|----> Difference à l'indice : 2 result.parents=1 et expectedResult.parents=0
[X] - Test : 2
|----> Difference à l'indice : 3 result.parents=1 et expectedResult.parents=2
[X] - Test : 3
|----> Difference à l'indice : 6 result.parents=7 et expectedResult.parents=5
[X] - Test : 4
|----> Difference à l'indice : 5 result.parents=4 et expectedResult.parents=-1
Resultat : [1/5]
Seul le test zéro passe, c’est normal, car tous les sommets ont des valeurs différentes et aucune somme ne donne le même résultat. ### Deuxième mutant :
// TestGraph.java ligne 67
// "!=" devient "=="
// check if vertex was visited already
if (e.getEndPoint() == v.getId()) {
continue;
}Ce mutant est choisi, car il est fréquent de se tromper dans les oppérations logiques.
[X] - Test : 0
|----> Difference à l'indice : 1 result.distances=7.5 et expectedResult.distances=5.2
[X] - Test : 1
|----> Difference à l'indice : 1 result.distances=-4.3 et expectedResult.distances=-2.1
[X] - Test : 2
|----> Difference à l'indice : 3 result.parents=0 et expectedResult.parents=2
[X] - Test : 3
|----> Difference à l'indice : 1 result.distances=-8.0 et expectedResult.distances=2.0
[X] - Test : 4
|----> Difference à l'indice : 1 result.distances=-3.0 et expectedResult.distances=1.0
Resultat : [0/5]
Aucun test ne passe, ce qui est aussi normal. Ici on ne calcule plus le plus court chemin, car on peut passer dans des boucles.
// TestGraph.java ligne 72
// le "+" devient "-" v.setDistance(u.getDistance() - e.getWeight());
if (v.getDistance() > u.getDistance() + e.getWeight()) {
v.setDistance(u.getDistance() - e.getWeight());
v.setParent(u);
parents[v.getId()] = v.getParent().getId();
}Ce mutant est choisi, car il est intéressant de vérifier s’il n’y a pas une erreur dans l’implémentation.
[X] - Test : 0
|----> Difference à l'indice : 1 result.distances=-11.8 et expectedResult.distances=5.2
[X] - Test : 1
|----> Difference à l'indice : 1 result.distances=2.1 et expectedResult.distances=-2.1
[V] - Test : 2
[X] - Test : 3
|----> Difference à l'indice : 1 result.distances=-2.0 et expectedResult.distances=2.0
[X] - Test : 4
|----> Difference à l'indice : 1 result.distances=-1.0 et expectedResult.distances=1.0
Resultat : [1/5]
Seul le test deux est validé, car il n’y a que des zéros et zéro est le neutre de l’addition.
if (v.getDistance() > u.getDistance() + e.getWeight()) {
v.setDistance(u.getDistance() + e.getWeight());
v.setParent(v);
parents[v.getId()] = v.getParent().getId();
}Ce mutant est choisi, car les noms des variables sont mal choisies “u” et “v” sont deux lettres très ressemblante, il est facile de les confondre.
[X] - Test : 0
|----> Difference à l'indice : 1 result.parents=1 et expectedResult.parents=0
[X] - Test : 1
|----> Difference à l'indice : 1 result.parents=1 et expectedResult.parents=0
[X] - Test : 2
|----> Difference à l'indice : 1 result.parents=1 et expectedResult.parents=0
[X] - Test : 3
|----> Difference à l'indice : 1 result.parents=1 et expectedResult.parents=0
[X] - Test : 4
|----> Difference à l'indice : 1 result.parents=1 et expectedResult.parents=0
Resultat : [0/5]
Le mutant démontre qu’il n’y a pas eu d’erreur.